/* 次小生成树
* 最小生成树算法解析
* Prim 朴素 O(n^2) 邻接矩阵 枚举点 不可堆优化 

* Krusal O(mlogm) 存边 维护连通性使用并查集 已是最小生成树，加任意一条边就存在环，此时需要判决

* 最小生成树理论基础:
* 1．任意一棵最小生成树一定可以包含无向图中权值最小的边。
* 2．给定一张无向图G=(V,E),n=|V|, m=|E|。从E中选出k<n-1条边构成G的加一个生成森林。
     然后在剩余的m-k条边中选n-1-k条边添加到生成森林中，使其成为G的生成树，并且选出的边的权值之和最小。
     则该生成树一定可以包含m-k条边中连接生成森林的两个不连通节点的权值最小的边。

* Krusal算法:
* 1.先将所有边按边权从小到大排序
* 2.从小到大扫描所有边, 依次将没有合并的点集合并
    假设当前已经循环完第i条边，已经求出了由前i条边所构成的

* 次小生成树
* 定义：给一个带权的图，把图的所有生成树按权值从小到大排序，第二小的称为次小生成树。
*      严格次小生成树：权值严格小于最小生成树。
*      非严格次小生成树：权值小于等于最小生成树。

* 方法1:先求最小生成树，再枚举删去最小生成树中的边求解。时间复杂度。0(mlogm +nm)
* 方法2:先求最小生成树，然后依次枚举非树边，然后将该边加入树中，同时从树中去掉一条边，使得最终的图仍是棵树。则一定可以求出次小生成树。

* 设T为图G的一棵生成树，对于非树边a和树边b，插入边a，并删除边b的操作记为(+a,-b)。
* 如果T+a-b之后，仍然是一棵生成树，称(+a,-b)是T的一个可行交换。
* 称由T进行一次可行变换所得到的新的生成树集合称为T的邻集。
* 定理:次小生成树一定在最小生成树的邻集中。

* 本题做法: 
* 1．求最小生成树，统计标记每条边是树边，还是非树边；同时把最小生成树建立出来。
* 2．预处理任意两点间的边权最大值dist[a][b]
* 3．依次枚举所有非树边，求min(sum +w-dist[a][b]), 满足w > dist[a][b]。

* 一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。
    n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元
    n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
    n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa
*/
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
// #define ONLINE_GUDGE
using namespace std;
#define int long long
const int N = 510, M = 10010, INF = 0x3f3f3f3f;

int n, m;

struct Edge{    //用结构体存储每条边
    int from, to;
    int w;
    bool f; // 是否在最小生成树中
    bool operator<(const Edge &e)const{
        return w < e.w;
    }
}edges[N];

int fa[N]; 
int dist[N][N];
int h[N], e[N*2], w[N*2], ne[N*2], idx;

void AddEdge(int a, int b, int c)
{ e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; }

int find(int x){    //并查集找根节点
    return fa[x] = (fa[x] == x ? x : find(fa[x]));
}

void dfs(int u, int fa, int maxd, int d[])
{
    d[u] = maxd;
    for(int i = h[u];i != -1;i = ne[i]){
        int v = e[i];
        // 防止往回走
        if(v != fa){
            dfs(v, u,  max(maxd, w[i]), d);
        }
    }

}

signed main()
{
    #ifdef ONLINE_JUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0); cin.tie(0);
    int T; T = 1;// cin >> T;
    while(T--)
    {

        cin >> n >> m;
        memset(h, -1, sizeof h);

        for(int i = 0; i < m; i++){
                int a, b, w; cin >> a >> b >> w;
                edges[i] = Edge{a, b, w};  //加入当前的边
            }
        sort(edges, edges+m);  //对边进行排序

        for(int i = 1; i <= n; i++) fa[i] = i;    //并查集初始化

        int sum = 0;

        for(int i = 0; i < m; i++){

            int f = edges[i].from, t = edges[i].to, w = edges[i].w;
            int ff = find(f), ft = find(t);

            if(ff != ft){   //当前两点不连通
                sum += w;
                fa[f] = t;    //让两点变连通
                AddEdge(f, t, w); AddEdge(t, f, w);
                edges[i].f = true;
            }
        }

        for(int u = 1; u <= n; u++) dfs(u, -1, 0, dist[u]);

        int res = 1e18;
  
        for(int i = 0; i < m; i++)
            if(!edges[i].f)
            {
                int f = edges[i].from, t = edges[i].to, w = edges[i].w;
                if(w > dist[f][t])
                    res = min(res, sum + w - dist[f][t]);
                    // printf("res:%lld sum:%lld w:%lld dist:%lld cal:%lld\n", res, sum, w, dist[f][t], sum + w - dist[f][t]);
            }
        printf("%lld", res);
    }
    return 0;
} 